#include "hash_table.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <string>

bool g_print_html = !!getenv("QUERY_STRING");

using std::string;

// http://en.wikipedia.org/wiki/Pocket_Cube
class PocketCube {
 public:
  // Red/Green/Yellow/Purple/Blue/Dark
  static const char color_codes[];
  static const char* html_color_codes[];
  int ColorCodeToColorNum(char color_code) {
    for (int i = 0; i < 6; i++)
      if (color_code == color_codes[i])
        return i;
    assert(0);
  }
  char ColorNumToColorCode(int color_num) {
    assert(color_num >= 0 && color_num < 6);
    return color_codes[color_num];
  }
  PocketCube(const char* str) {
    assert(strlen(str) == 29);
    for (int i = 0; i < 6; i++) {
      for (int j = 0; j < 4; j++) {
        cube_[j + i * 4] = ColorCodeToColorNum(str[j + i * (4 + 1)]);
      }
    }
    Validate();
  }

  __attribute__((noinline)) PocketCube(uint64_t hash) {
    assert(hash < 789730223053602816ULL);
    uint64_t t = hash;
    for (size_t i = 23; i > 1; i--) {
      uint64_t rem = t % 6;
      cube_[i] = rem;
      t = (t - rem) / 6;
    }
    assert(t < 6);
    cube_[1] = t;
    cube_[0] = 0;
    // validateCube(cube);
    // printf("h1 %llu\n", hash);
    // printf("h2 %llu\n", cubeToHash(cube));
    assert(hash == Hash());
  }

  PocketCube() {}

  string ToString() {
    char str[30];
    Validate();
    size_t idx = 0;
    for (size_t i = 0; i < 6; i++) {
      for (size_t j = 0; j < 4; j++) {
        // printf("%d\n", idx);
        str[idx] = ColorNumToColorCode(cube_[j + i * 4]);
        idx++;
      }
      // printf("%d\n", idx);
      str[idx] = '-';
      idx++;
    }
    assert(idx == 30);
    // printf("%d\n", idx);
    str[idx - 1] = '\0';
    // printf("%s\n", str);
    return str;
  }

  string ToHtml() {
    string res;
    char buff[4000];
    char one_side[] =
        "<td> <table border='1'>"
        "<tr><td bgcolor='%s'>%c</td> <td bgcolor='%s'>%c</td> </tr>"
        "<tr><td bgcolor='%s'>%c</td> <td bgcolor='%s'>%c</td> </tr>"
        "</table> </td>";
    res = "<table> <tr>";
    for (int i = 0; i < 6; i++) {
      uint8_t a0 = cube_[i*4+0];
      uint8_t a1 = cube_[i*4+1];
      uint8_t a2 = cube_[i*4+2];
      uint8_t a3 = cube_[i*4+3];
      snprintf(buff, sizeof(buff), one_side,
               html_color_codes[a1], color_codes[a1],
               html_color_codes[a2], color_codes[a2],
               html_color_codes[a0], color_codes[a0],
               html_color_codes[a3], color_codes[a3]
               );
      res += buff;
    }
    res += "</table>";
    return res;
  }

  __attribute__((noinline)) uint64_t Hash() {
    uint64_t hash = 0;
    for (size_t i = 1; i < 23; i++) {
      hash = (hash + cube_[i]) * 6;
    }
    hash += cube_[23];
    assert(hash < 789730223053602816ULL);
    return hash;
  }

  __attribute__((noinline)) PocketCube RotateRight() {
    PocketCube t;
    t.cube_[0] = cube_[0];
    t.cube_[1] = cube_[1];
    t.cube_[2] = cube_[22];
    t.cube_[3] = cube_[23];
    t.cube_[4] = cube_[7];
    t.cube_[5] = cube_[4];
    t.cube_[6] = cube_[5];
    t.cube_[7] = cube_[6];
    t.cube_[8] = cube_[18];
    t.cube_[9] = cube_[19];
    t.cube_[10] = cube_[10];
    t.cube_[11] = cube_[11];
    t.cube_[12] = cube_[12];
    t.cube_[13] = cube_[13];
    t.cube_[14] = cube_[14];
    t.cube_[15] = cube_[15];
    t.cube_[16] = cube_[16];
    t.cube_[17] = cube_[17];
    t.cube_[18] = cube_[2];
    t.cube_[19] = cube_[3];
    t.cube_[20] = cube_[20];
    t.cube_[21] = cube_[21];
    t.cube_[22] = cube_[8];
    t.cube_[23] = cube_[9];
    return t;
  }

  __attribute__((noinline)) PocketCube RotateTop() {
    PocketCube t;
    t.cube_[0] = cube_[0];
    t.cube_[1] = cube_[5];
    t.cube_[2] = cube_[6];
    t.cube_[3] = cube_[3];
    t.cube_[4] = cube_[4];
    t.cube_[5] = cube_[9];
    t.cube_[6] = cube_[10];
    t.cube_[7] = cube_[7];
    t.cube_[8] = cube_[8];
    t.cube_[9] = cube_[13];
    t.cube_[10] = cube_[14];
    t.cube_[11] = cube_[11];
    t.cube_[12] = cube_[12];
    t.cube_[13] = cube_[1];
    t.cube_[14] = cube_[2];
    t.cube_[15] = cube_[15];
    t.cube_[16] = cube_[19];
    t.cube_[17] = cube_[16];
    t.cube_[18] = cube_[17];
    t.cube_[19] = cube_[18];
    t.cube_[20] = cube_[20];
    t.cube_[21] = cube_[21];
    t.cube_[22] = cube_[22];
    t.cube_[23] = cube_[23];
    return t;
  }

  __attribute__((noinline)) PocketCube RotateBack() {
    PocketCube t;
    t.cube_[0] = cube_[0];
    t.cube_[1] = cube_[1];
    t.cube_[2] = cube_[2];
    t.cube_[3] = cube_[3];
    t.cube_[4] = cube_[4];
    t.cube_[5] = cube_[5];
    t.cube_[6] = cube_[23];
    t.cube_[7] = cube_[20];
    t.cube_[8] = cube_[11];
    t.cube_[9] = cube_[8];
    t.cube_[10] = cube_[9];
    t.cube_[11] = cube_[10];
    t.cube_[12] = cube_[17];
    t.cube_[13] = cube_[18];
    t.cube_[14] = cube_[14];
    t.cube_[15] = cube_[15];
    t.cube_[16] = cube_[16];
    t.cube_[17] = cube_[6];
    t.cube_[18] = cube_[7];
    t.cube_[19] = cube_[19];
    t.cube_[20] = cube_[13];
    t.cube_[21] = cube_[21];
    t.cube_[22] = cube_[22];
    t.cube_[23] = cube_[12];
    return t;
  }

  __attribute__((noinline)) void GenMoves(PocketCube moves[9]) {
    PocketCube t;
    moves[0] = this->RotateRight();
    moves[1] = moves[0].RotateRight();
    moves[2] = moves[1].RotateRight();
    t = moves[2].RotateRight();
    assert(!memcmp(this, &t, sizeof(t)));

    moves[3] = this->RotateTop();
    moves[4] = moves[3].RotateTop();
    moves[5] = moves[4].RotateTop();
    t = moves[5].RotateTop();
    assert(!memcmp(this, &t, sizeof(t)));

    moves[6] = this->RotateBack();
    moves[7] = moves[6].RotateBack();
    moves[8] = moves[7].RotateBack();
    t = moves[8].RotateBack();
    assert(!memcmp(this, &t, sizeof(t)));
  }

  static const char* MoveToString(int move) {
    switch (move) {
      case 0:
        return "Right 1";
      case 1:
        return "Right 2";
      case 2:
        return "Right 3";
      case 3:
        return "Top 1";
      case 4:
        return "Top 2";
      case 5:
        return "Top 3";
      case 6:
        return "Back 1";
      case 7:
        return "Back 2";
      case 8:
        return "Back 3";
      default:
        assert(0);
    }
  }

  void Validate() {
    assert(cube_[0] == 0);
    assert(cube_[15] == 1);
    assert(cube_[21] == 2);
    for (size_t i = 0; i < 24; i++)
      assert(cube_[i] < 6);
    // TODO: add more.
  }

 private:
  uint8_t cube_[24];
};

const char PocketCube::color_codes[] = "RGYPBD";
const char* PocketCube::html_color_codes[] = {"red", "green", "yellow",
                                              "purple", "blue", "gray"};

void BFS(PocketCube c0, uint64_t max_depth, HashTable* ht0, HashTable* ht1) {
  ht0->Insert(c0.Hash(), 0);
  assert(ht0->n_inserts() == 1);
  for (uint64_t depth = 1; depth <= max_depth; depth++) {
    for (size_t i = 0; i < ht0->size(); i++) {
      uint64_t h = ht0->raw(i);
      if (!h)
        continue;
      // printf("raw: %zd\n", i);
      uint64_t elem_depth = h >> 60;
      uint64_t elem_hash = (h << 4) >> 4;
      if (elem_depth != depth - 1)
        continue;
      PocketCube c(elem_hash);
      PocketCube moves[9];
      c.GenMoves(moves);
      uint64_t hashes[9];
      for (int m = 0; m < 9; m++)
        hashes[m] = moves[m].Hash();
      for (int m = 0; m < 9; m++)
        ht0->Insert(hashes[m], depth);
    }
    if (!g_print_html) {
      printf("depth: %02ld: % 8zd inserts; % 9zd lookups; % 9zd collisions\n",
             depth,
             ht0->n_inserts(),
             ht0->n_lookups(),
             ht0->n_collisions());
      fflush(stdout);
    }
  }
}

uint64_t DecreasedDepthMove(uint64_t key, HashTable* ht) {
  uint64_t d = ht->GetVal(key);
  assert(d > 0);
  PocketCube c(key);
  PocketCube moves[9];
  c.GenMoves(moves);
  for (int m = 0; m < 9; m++) {
    uint64_t hash = moves[m].Hash();
    uint64_t keyval = ht->FindKey(hash);
    if (!keyval)
      continue;
    if (ExtractVal(keyval) < d)
      return hash;
  }
  assert(0);
  return 0;
}

int FindMove(uint64_t from, uint64_t to) {
  PocketCube c(from);
  PocketCube moves[9];
  c.GenMoves(moves);
  for (int i = 0; i < 9; i++)
    if (moves[i].Hash() == to)
      return i;
  assert(0);
  return 0;
}

int ReconstructPath(PocketCube& c0,
                    PocketCube& c1,
                    uint64_t midkey,
                    HashTable* ht0,
                    HashTable* ht1,
                    uint64_t positions[12],
                    int moves[12]) {
  int d0 = ht0->GetVal(midkey);
  int d1 = ht1->GetVal(midkey);
  assert(d0 + d1 <= 11);
  positions[d0] = midkey;
  for (int i = d0; i > 0; i--)
    positions[i - 1] = DecreasedDepthMove(positions[i], ht0);
  for (int i = d0; i < d0 + d1; i++)
    positions[i + 1] = DecreasedDepthMove(positions[i], ht1);

  for (int i = 0; i < d0 + d1; i++)
    moves[i] = FindMove(positions[i], positions[i + 1]);

  return d0 + d1;
}

void Search(PocketCube& c0, PocketCube& c1) {
  HashTable* ht0 = new HashTable(18);
  HashTable* ht1 = new HashTable(18);
  if (g_print_html) {
    printf("Content-Type: text/html; charset=ISO-8859-1\n\n");
    printf("<html><pre>\n");
  }
  // For simplicity, search for max combined depth. It's still fast enough.
  BFS(c0, 6, ht0, 0);
  BFS(c1, 5, ht1, ht0);
  uint64_t best_key = 0;
  uint64_t best_depth = 100000;
  for (size_t i = 0; i < ht1->size(); i++) {
    uint64_t kv1 = ht1->raw(i);
    if (!kv1)
      continue;
    uint64_t kv0 = ht0->FindKey(ExtractKey(kv1));
    if (!kv0)
      continue;
    uint64_t d0 = ExtractVal(kv0);
    uint64_t d1 = ExtractVal(kv1);
    assert(ExtractKey(kv0) == ExtractKey(kv1));
    if (d0 + d1 < best_depth) {
      best_depth = d0 + d1;
      best_key = ExtractKey(kv1);
    }
  }
  uint64_t positions[12];
  int moves[12];
  int depth = ReconstructPath(c0, c1, best_key, ht0, ht1, positions, moves);
  for (int i = 0; i <= depth; i++) {
    printf("[%02d] %016lx %s: %s\n",
           i,
           positions[i],
           PocketCube(positions[i]).ToString().c_str(),
           i == depth ? "done" : PocketCube::MoveToString(moves[i]));
  }
  if (g_print_html) {
    printf("</pre>\n");
    for (int i = 0; i <= depth; i++) {
      printf("%s\n", PocketCube(positions[i]).ToHtml().c_str());
      if (i != depth)
        printf("%s<BR>\n", PocketCube::MoveToString(moves[i]));
    }
    printf("</html>\n");
  }

  delete ht0;
  delete ht1;
}

static void TestPocketCube() {
  PocketCube c("RRRR-BBBB-PPPP-GGGG-DDDD-YYYY");
  PocketCube c1(c.Hash());
  assert(c.Hash() == c1.Hash());
  assert(c.ToString() == c1.ToString());
  PocketCube moves[9];
  c.GenMoves(moves);
  assert(moves[0].ToString() == "RRYY-BBBB-DDPP-GGGG-DDRR-YYPP");
  assert(moves[1].ToString() == "RRPP-BBBB-RRPP-GGGG-DDYY-YYDD");
  assert(moves[2].ToString() == "RRDD-BBBB-YYPP-GGGG-DDPP-YYRR");
  assert(moves[3].ToString() == "RBBR-BPPB-PGGP-GRRG-DDDD-YYYY");
  assert(moves[4].ToString() == "RPPR-BGGB-PRRP-GBBG-DDDD-YYYY");
  assert(moves[5].ToString() == "RGGR-BRRB-PBBP-GPPG-DDDD-YYYY");
  assert(moves[6].ToString() == "RRRR-BBYY-PPPP-DDGG-DBBD-GYYG");
  assert(moves[7].ToString() == "RRRR-BBGG-PPPP-BBGG-DYYD-DYYD");
  assert(moves[8].ToString() == "RRRR-BBDD-PPPP-YYGG-DGGD-BYYB");
}

int main(int argc, char** argv) {
  TestHashTable();
  TestPocketCube();
  PocketCube target("RRRR-BBBB-PPPP-GGGG-DDDD-YYYY");
  if (argc == 1) {
    HashTable *ht = new HashTable(24);
    BFS(target, 12, ht, 0);
    if (0) {
      for (size_t i = 0; i < ht->size(); i++) {
        uint64_t h = ht->raw(i);
        if (!h)
          continue;
        uint64_t elem_depth = h >> 60;
        uint64_t elem_hash = (h << 4) >> 4;
        printf("%d: %s\n",
               (int)elem_depth,
               PocketCube(elem_hash).ToString().c_str());
      }
    }
    return 0;
  }
  if (argc == 2) {
    PocketCube c0(argv[1]);
    Search(c0, target);
    return 0;
  }
}
